package leetcode_1100;

import java.util.Arrays;
import java.util.LinkedList;

/**
 *@author 周杨 
 *PreviousPermutationWithOneSwap_1053_ 一个数组 找到比它小的最大排列 只能交换一次位置的元素
 *describe:我们只需要找到第一个递减 然后找出后面这个区间里 这样两个数 他们是递减的 并且第一数越靠后越好
 *那么我们就从后往前找 找到的第一个满足这个规则就可以交换
 *2019年5月26日 下午13:40
 */
public class PreviousPermutationWithOneSwap_1053_ {
	public static void main(String[] args) {
		PreviousPermutationWithOneSwap_1053_ test = new PreviousPermutationWithOneSwap_1053_();
		System.out.println(Arrays.toString(test.prevPermOpt1(new int[] {3,1,1,3})));
		//System.out.println(Arrays.toString(test.prevPermOpt1(new int[] {3,2,1})));
	}
	
	
	public int[] prevPermOpt1(int[] A) {
	       	boolean found = false;
	        int index = 0;
	        int i=A.length-1;
	        while (i >= 0) {//每个元素都找一次 除非找到了
	            int MaxOfMin = 0;//每次最多比较到这里 
	            for(int j=i+1; j<A.length; j++) {//在之后的区间内 找一个元素能够小于其的最大值
	                if(A[j] < A[i] && A[j] > MaxOfMin) {
	                    MaxOfMin = A[j];
	                    index = j;
	                    found = true;
	                }
	            }
	            if(found) break;  
	            i--;
	        };
	        if(found) {
	            int temp = A[i];
	            A[i] = A[index];
	            A[index] = temp;
	        }
	        return A;
	    }
	
	//不知道哪里出错了
	public int[] prevPermOpt1_(int[] A) {
		if(A.length == 1) return A;
		int start = 0;//找到第一个非递减的
		while(start < A.length-1 && A[start] <= A[start+1]) {
            ++start;
		}
		if(start == A.length-1) return A;//整个数组都是非递减的
		LinkedList<Integer> list = new LinkedList<>();//用双端队列
		list.add(start++);//里面存index 就能保证数组里的元素是唯一的了
		list.add(start++);
		while(start < A.length) {
			if(A[start] > A[list.getFirst()]) {
				++start;//大于队列头的不考虑
				continue;
			}
			if(A[start] < A[list.getLast()]) {//开始清空队列之前的元素 找到了递减的最大值
				int temp = list.getLast();
				list.clear();
				list.add(temp);
			}
			list.add(start);
			start++;
		}
		while(true) {//开始校验
			int last = list.pollLast();
			if(A[last] == A[list.getFirst()] || A[list.getLast()] == A[last]) continue;
			list.add(last);
			break;
		}
		int temp = A[list.getFirst()];//队列头
		A[list.getFirst()] = A[list.getLast()];
		A[list.getLast()] = temp; 
        return A;
    }
}
